#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;



string longestPalindrome(string s) {
    int i,j,k,d=0;
    int size = s.size();
    bool isTarget = false;
    string goal = string(&s[0],&s[1]);

    for(i = 1;i < size;i++)
    {
        for(j = 0;j < i;j++)
        {
//            cout<<(i-j-1)/2<<endl;
            for(k = 0;k <= (i-j-1)/2;k++)
            {
                if(!(s[j+k] == s[i-k]))
                {
                    isTarget = false;
                    break;
                }
                isTarget = true;
            }
//            cout<<s[j]<<","<<s[i]<<endl;
            if(isTarget && i-j+1>d)
            {
                goal = string(&s[j],&s[i+1]);
                d = i-j+1;
            }
        }
    }
    return goal;
}

string longestPalindrome2(string s) {
    int i,j,k,d=0;
    int size = s.size();
    bool isTarget = false;
    string goal = string(&s[0],&s[1]);
    string a,b;

    for(i = 1;i < size;i++)
    {
        for(j = 0;j < i;j++)
        {
            a = string(&s[j],&s[i+1]);
            b = a;
            cout<<a<<endl;
            reverse(b.begin(),b.end());

            if(a == b && i-j+1>d)
            {
                goal = a;
                d = i-j+1;
            }
        }
    }
    return goal;
}

string longestPalindrome3(string s) {
    int i,j,d=0;
    int size = s.size();
    string goal = string(&s[0],&s[1]);
    if(size == 0)
    {
        return goal;
    }
    bool dp[size][size] = {0};

    for(i = 1;i < size;i++)
    {
        for(j = 0;j <= i;j++)
        {
            if(s[j] == s[i] && (j>=i-2 || dp[j+1][i-1]))
            {
                dp[j][i] = true;
                if(i-j+1 > d)
                {
                    d = i-j+1;
                    goal = string(&s[j],&s[i+1]);
                }
            }
        }
    }
    return goal;
}

int main() {

//    string a = "abcdef";
//    string b = a;
//    reverse(b.begin(),b.end());
//    cout<<a<<","<<b<<endl;
    cout<<longestPalindrome3("abcdef")<<endl;
    return 0;
}